﻿/**
 * struct TreeNode {
 * int val;
 * struct TreeNode *left;
 * struct TreeNode *right;
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution
{
public:
	bool IsBalanced_Solution(TreeNode* pRoot)
	{
		return dfs(pRoot) != -1;
	}
	int dfs(TreeNode* root) // 返回值不是 -1 的话，其余的返回值表⽰的是树⾼ 
	{
		if (root == nullptr) return 0;
		int left = dfs(root->left);
		if (left == -1) return -1; // 剪枝 
		int right = dfs(root->right);
		if (right == -1) return -1;
		return abs(left - right) <= 1 ? max(left, right) + 1 : -1;
	}
};
